package cn.com.guage.dtm;

// 定义链表节点类
class ListNode<T> {
    T data;
    ListNode<T> next;

    // 构造函数，用于初始化节点数据
    public ListNode(T data) {
        this.data = data;
        this.next = null;
    }
}

// 定义链表类
class LinkedList<T> {
    private ListNode<T> head;
    private int size;

    // 构造函数，初始化链表
    public LinkedList() {
        this.head = null;
        this.size = 0;
    }

    // 获取链表的长度
    public int size() {
        return size;
    }

    // 判断链表是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 在链表末尾添加元素
    public void add(T data) {
        ListNode<T> newNode = new ListNode<T>(data);
        if (head == null) {
            head = newNode;
        } else {
            ListNode<T> current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
        size++;
    }

    // 在指定位置插入元素
    public void add(int index, T data) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        ListNode<T> newNode = new ListNode<>(data);
        if (index == 0) {
            newNode.next = head;
            head = newNode;
        } else {
            ListNode<T> current = head;
            for (int i = 0; i < index - 1; i++) {
                current = current.next;
            }
            newNode.next = current.next;
            current.next = newNode;
        }
        size++;
    }

    // 获取指定位置的元素
    public T get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        ListNode<T> current = head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.data;
    }

    // 删除指定位置的元素
    public T remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        T removedData;
        if (index == 0) {
            removedData = head.data;
            head = head.next;
        } else {
            ListNode<T> current = head;
            for (int i = 0; i < index - 1; i++) {
                current = current.next;
            }
            removedData = current.next.data;
            current.next = current.next.next;
        }
        size--;
        return removedData;
    }

    // 查找元素在链表中的位置
    public int indexOf(T data) {
        ListNode<T> current = head;
        int index = 0;
        while (current != null) {
            if (current.data.equals(data)) {
                return index;
            }
            current = current.next;
            index++;
        }
        return -1;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        ListNode<T> current = head;
        while (current != null) {
            sb.append(current.data);
            if (current.next != null) {
                sb.append(" -> ");
            }
            current = current.next;
        }
        return sb.toString();
    }
}

public class LinkedListImplementation {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        // 添加元素
        list.add(1);
        list.add(2);
        list.add(3);
        System.out.println("添加元素后: " + list);

        // 在指定位置插入元素
        list.add(1, 4);
        System.out.println("在位置 1 插入元素后: " + list);

        // 获取指定位置的元素
        System.out.println("位置 2 的元素是: " + list.get(2));

        // 删除指定位置的元素
        list.remove(1);
        System.out.println("删除位置 1 的元素后: " + list);

        // 查找元素的位置
        System.out.println("元素 3 的位置是: " + list.indexOf(3));
    }
}    